package leetcode.hot100;

public class number42 {
    public static void main(String[] args) {
        int trap = trap(new int[]{4, 2, 0, 3, 2, 5});
        System.out.println(trap);
    }
    public static int trap(int[] height) {
        return jieyushui(height,0,height.length-1);
    }
    public static int jieyushui(int[]height,int l,int r){
        if(l>=r||l==-1||r==-1){
            return 0;
        }
        int sum=0;
        int heigest=0;
        int heigestIndex=-1;
        for(int i=l;i<=r;i++){
            if(height[i]>heigest){
                heigest=height[i];
                heigestIndex=i;
            }
        }
        int heigestLeft=0;
        int heigestLeftIndex=-1;
        for(int i=l;i<heigestIndex;i++){
            if(height[i]>heigestLeft){
                heigestLeft=height[i];
                heigestLeftIndex=i;
            }
        }

        int heigestRight=0;
        int heigestRightIndex=-1;
        for(int i=r;i>heigestIndex;i--){
            if(height[i]>heigestRight){
                heigestRight=height[i];
                heigestRightIndex=i;
            }
        }

        int ll=heigestLeftIndex;
        int rr=heigestRightIndex;
        int mm=heigestIndex;

        if(heigestLeftIndex!=-1)
            while(++ll<mm){
                sum+=height[heigestLeftIndex]-height[ll];
            }

        if(heigestRightIndex!=-1)
            while(--rr>mm){
                sum+=height[heigestRightIndex]-height[rr];
            }

        return sum
                +jieyushui(height,l,heigestLeftIndex)
                +jieyushui(height,heigestRightIndex,r);
    }
}

